Search for: All records

Abstract For a subset$$A$$of an abelian group$$G$$, given its size$$|A|$$, its doubling$$\kappa =|A+A|/|A|$$, and a parameter$$s$$which is small compared to$$|A|$$, we study the size of the largest sumset$$A+A'$$that can be guaranteed for a subset$$A'$$of$$A$$of size at most$$s$$. We show that a subset$$A'\subseteq A$$of size at most$$s$$can be found so that$$|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$$. Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling$$\kappa$$is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets$$A,B$$of$$\mathbb{F}_p$$of size at most$$\alpha p$$for an appropriate constant$$\alpha \gt 0$$, one only needs three elements$$b_1,b_2,b_3\in B$$to guarantee$$|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$$. Allowing the use of larger subsets$$A'$$, we show that for sets$$A$$of bounded doubling, one only needs a subset$$A'$$with$$o(|A|)$$elements to guarantee that$$A+A'=A+A$$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset. 

We develop a quantitative large deviations theory for random hypergraphs, which rests on tensor decomposition and counting lemmas under a novel family of cut-type norms. As our main application, we obtain sharp asymptotics for joint upper and lower tails of homomorphism counts in the r-uniform Erdo ̋s–Rényi hypergraph for any fixed r≥2, generalizing and improving on previous results for the Erdo ̋s–Rényi graph (r=2). The theory is sufficiently quantitative to allow the density of the hypergraph to vanish at a polynomial rate, and additionally yields tail asymptotics for other nonlinear functionals, such as induced homomorphism counts. 

We introduce a notion called entropic independence that is an entropic analog of spectral notions of high-dimensional expansion. Informally, entropic independence of a background distribution $$\mu$$ on $$k$$-sized subsets of a ground set of elements says that for any (possibly randomly chosen) set $$S$$, the relative entropy of a single element of $$S$$ drawn uniformly at random carries at most $O(1/k)$ fraction of the relative entropy of $$S$$. Entropic independence is the analog of the notion of spectral independence, if one replaces variance by entropy. We use entropic independence to derive tight mixing time bounds, overcoming the lossy nature of spectral analysis of Markov chains on exponential-sized state spaces. In our main technical result, we show a general way of deriving entropy contraction, a.k.a. modified log-Sobolev inequalities, for down-up random walks from spectral notions. We show that spectral independence of a distribution under arbitrary external fields automatically implies entropic independence. We furthermore extend our theory to the case where spectral independence does not hold under arbitrary external fields. To do this, we introduce a framework for obtaining tight mixing time bounds for Markov chains based on what we call restricted modified log-Sobolev inequalities, which guarantee entropy contraction not for all distributions, but for those in a sufficiently large neighborhood of the stationary distribution. To derive our results, we relate entropic independence to properties of polynomials: $$\mu$$ is entropically independent exactly when a transformed version of the generating polynomial of $$\mu$$ is upper bounded by its linear tangent; this property is implied by concavity of the said transformation, which was shown by prior work to be locally equivalent to spectral independence. We apply our results to obtain (1) tight modified log-Sobolev inequalities and mixing times for multi-step down-up walks on fractionally log-concave distributions, (2) the tight mixing time of $$O(n\log n)$$ for Glauber dynamics on Ising models whose interaction matrix has eigenspectrum lying within an interval of length smaller than $$1$$, improving upon the prior quadratic dependence on $$n$$, and (3) nearly-linear time $$\widetilde O_{\delta}(n)$$ samplers for the hardcore and Ising models on $$n$$-node graphs that have $$\delta$$-relative gap to the tree-uniqueness threshold. In the last application, our bound on the running time does not depend on the maximum degree $$\Delta$$ of the graph, and is therefore optimal even for high-degree graphs, and in fact, is sublinear in the size of the graph for high-degree graphs. 

Abstract A linear equation with coefficients in $$\mathbb{F}_q$$ is common if the number of monochromatic solutions in any two-coloring of $$\mathbb{F}_q^{\,n}$$ is asymptotically (as $$n \to \infty$$) at least the number expected in a random two-coloring. The linear equation is Sidorenko if the number of solutions in any dense subset of $$\mathbb{F}_q^{\,n}$$ is asymptotically at least the number expected in a random set of the same density. In this paper, we characterize those linear equations which are common, and those which are Sidorenko. The main novelty is a construction based on choosing random Fourier coefficients that shows that certain linear equations do not have these properties. This solves problems posed in a paper of Saad and Wolf. 

Green used an arithmetic analogue of Szemerédi's celebrated regularity lemma to prove the following strengthening of Roth's theorem in vector spaces. For every α>0, β<α3, and prime number p, there is a least positive integer n_p(α,β) such that if n≥n_p(α,β), then for every subset of 𝔽np of density at least α there is a nonzero d for which the density of three-term arithmetic progressions with common difference d is at least β. We determine for p≥19 the tower height of n_p(α,β) up to an absolute constant factor and an additive term depending only on p. In particular, if we want half the random bound (so β=α^{3}/2), then the dimension n required is a tower of twos of height Θ((log p)loglog(1/α)). It turns out that the tower height in general takes on a different form in several different regions of α and β, and different arguments are used both in the upper and lower bounds to handle these cases.